package com.peng.leetcode.other;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * SolveNQueens
 * n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
 *
 * @author: lupeng6
 * @create: 2020/11/27 14:16
 */
public class SolveNQueens {

    public static void main(String[] args) {
//        List<List<String>> lists = new Solution1().solveNQueens(5);
//        for (List<String> list : lists) {
//            System.out.println("------------------------");
//            for (String s : list) {
//                System.out.println(s);
//            }
//        }

//        System.out.println(Integer.toBinaryString(3));
//        System.out.println(Integer.toBinaryString(-3));
//        System.out.println(Integer.toBinaryString(Integer.MIN_VALUE));
//
//        System.out.println(Integer.toBinaryString(4));
//        System.out.println(Integer.toBinaryString(-4));
        
        System.out.println();
    }

    static class Solution1 {
        public List<List<String>> solveNQueens(int n) {
            List<List<String>> res = new ArrayList<>();
            Set<Integer> excludeCols = new HashSet<>();
            Set<Integer> excludeDias = new HashSet<>();
            Set<Integer> excludeDias1 = new HashSet<>();
            int[] queens = new int[n];
            Arrays.fill(queens, -1);
            dfs(n, 0, queens, excludeCols, excludeDias, excludeDias1, res);
            return res;
        }

        private void dfs(int n, int row, int[] queens, Set<Integer> excludeCols, Set<Integer> excludeDias, Set<Integer> excludeDias1, List<List<String>> res) {
            if (n == row) {
                res.add(genBoard(n, queens));
                return;
            }

            for (int i = 0; i < n; i++) {
                if (excludeCols.contains(i)) {
                    continue;
                }
                int dia = i - row;
                int dia1 = i + row;
                if (excludeDias.contains(dia)) {
                    continue;
                }
                if (excludeDias1.contains(dia1)) {
                    continue;
                }
                queens[row] = i;
                excludeCols.add(i);
                excludeDias.add(dia);
                excludeDias1.add(dia1);

                dfs(n, row + 1, queens, excludeCols, excludeDias, excludeDias1, res);

                queens[row] = -1;
                excludeCols.remove(i);
                excludeDias.remove(dia);
                excludeDias1.remove(dia1);
            }
        }

        private List<String> genBoard(int n, int[] queens) {
            List<String> list = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                char[] str = new char[n];
                Arrays.fill(str, '.');
                if (queens[i] >= 0) {
                    str[queens[i]] = 'Q';
                }
                list.add(new String(str));
            }
            return list;
        }
    }

}
